1. Field of the Invention
The present invention relates generally to data flow type information processors, and more particularly, to a data flow type information processor for processing data in accordance with a data flow program.
2. Description of The Prior Art
In a conventional von Neumann computer, various instructions as programs are stored in advance in a program memory, and addresses in the program memory are sequentially specified by a program counter so that the instruction are sequentially read out, whereby the instruction are executed.
On the other hand, a data flow type information processor is a kind of a non-von Neumann computer having no concept of sequential execution of instruction by a program counter. Such a data flow type information processor employs architecture based on parallel processing of instructions. In the data flow type information processor, immediately after data to be objects of an operation are collected, an instruction can be executed, and a plurality of instructions are simultaneously driven by the data, so that programs are executed in parallel in accordance with natural flow of the data. As a result, it is considered that the time required for the operation is significantly reduced.
FIG. 1 is a block diagram showing one example of a structure of a conventional data flow type information processor, and FIG. 2 is a diagram showing one example of field structure of a data packet processed by the information processor.
The data packet shown in FIG. 2 comprises a through packet flag, a color field, a destination field, an instruction field, a data 1 field, and a data 2 field. The color field stores color information, the destination field stores destination information, the instruction field stores instruction information, and the data 1 field or the data 2 field stores operand data.
The information processor shown in FIG. 1 comprises a program storing means 1, a data pair producing means 2, and a processing means 3. The program storing means 1 contains a program memory (not shown) in which the data flow program comprising the destination information and the instruction information, as shown in FIG. 3, are stored. The program storing means 1 reads out the destination information and the instruction information in the data flow program, by addressing based on destination information in an inputted data packet; stores the destination information and the instruction information in the destination field and the instruction field in the data packet, respectively; and outputs that data packet. The data pair producing means 2 queues the data packet outputted from the program storing means 1. More specifically, the data pair producing means 2 detects different two data packets having the same color information and destination information; stores operand data in one of the data packets, for example, the content of the data 1 field shown in FIG. 2, in the data 2 field in the other data packet; and outputs the other data packet. At that time, the above described one data packet disappears. The processing means 3 decodes the instruction information in the data packet outputted from the data pair producing means 2 and performs processing based on the decoded instruction information with respect to the two operand data in the data packet. Then, the result of the processing is stored in the data 1 field, for example, in the data packet and the data packet is outputted to the program storing means 1.
Meanwhile, the program storing means 1 and the data pair producing means 2 are coupled to each other by two data transmission paths 4 and 5. The data transmission paths 4 and 5 are coupled to two input ports of the data pair producing means 2. The data packet outputted from the program storing means 1 is selectively inputted to either one of the input ports of the data pair producing means 2, depending on whether the operand data is a right operand data or a left operand data in the processing. In addition, the data pair producing means 2 and the processing means 3 are coupled to each other by a transmission path 6, and the processing means 3 and the program storing means 1 are coupled to each other by a transmission path 7.
The data packet circulates through the program storing means 1, the data pair producing means 2, and the processing means 3 in that order, so that the processing based on the data flow program stored in the program storing means 1 progresses.
The data pair producing means 2 detects paired data based on a so-called template matching scheme. Conventionally, such template matching scheme using a matching memory such as a random access memory (RAM) and a serial access memory (SAM) is known.
As described in the forgoing, when a matching memory is used as the data pair producing means 2, it has been proposed, as seen in papers for lecture in the 34th Meeting in Japan by Information Processing Association, 2Q-7, pages 249, 250 (1987), that physical address space of the matching memory can be effectively utilized by using, as an address, value which is obtained by applying hash operation to the color information stored in the color field and the destination information stored in the destination field shown in FIG. 2, for access to the matching memory. In a system of accessing a matching memory by the hashed address (simply referred to as "hash address" hereinafter), it is likely that execution of processing could not continue because accessing contention occurs with respect to a plurality of different data having the same hash address (referred to as "hash collision" hereinafter). Then, "a data exchanging system" is proposed as measure for hash collision in the above described paper. In this data exchanging system, the data pair producing means 2 performs the following operations (1) to (6). In this connection, it is assumed that all of the presence bits (PB) of the data in the matching memory shown in FIG. 4 are set to "invalid" before execution of the data flow program starts.
(1) A hash operation is applied to the color information and the destination information in an input data packet shown in FIG. 2, and by using the obtained value as an address, the data shown in FIG. 4 is read out from the matching memory. PA1 (2) If and when the presence bit (PB) in data read out from the matching memory is "invalid", the color information, the destination information and the contents in the data 1 field in the input data packet are written into the matching memory in accordance with the hash address and the PB is set to "valid", so that the processing is terminated. On the other hand, if the PB in the data read out from the matching memory is "valid", the processing in the following (3) is performed. PA1 (3) The numerical value represented by the color information and the destination information in the input data packet is compared with a numerical value represented by the color information and the destination information in the data read out from the matching memory, and if the numerical value in the input data packet is larger than that from the matching memory, the following processing (4) is performed; if smaller, the following processing (5) is performed; and if both are coincident with each other, the following processing (6) is performed. PA1 (4) A through packet flag in the input data packet shown in FIG. 2 is set to "valid", and then, is sent out from the data pair producing means 2, so that the processing is terminated. PA1 (5) Based on the data read out from the matching memory, a new data packet is produced, and, in addition, a through packet flag in the newly produced data packet is set to "valid" and then is sent out to the processing means 3. Color information, destination information, instruction information and a content in the data 1 field in the input data packet are written into an area of the matching memory designated by a hash address and then the processing is terminated. PA1 (6) A data pair is produced by combining the contents in the data field in the input data packet (one operand data) with the content in the data field read out from the matching memory (the other operand data), and, in addition, a new data packet is produced by adding to the data pair the contents of color information, destination information and instruction information in the input data packet. Then, a through packet flag in the newly produced data packet is set to "invalid" and then sent out to the processing means 3. Furthermore, the PB in the area of the matching memory designated in the hash address is set to "invalid", so that the processing is terminated.
Meanwhile, the data packet having a "valid" through packet flag, which is sent out from the data pair producing means 2, passes through the processing means 3 and the program storing means 1, without being processed in the processing means 3 and the storing means 1, and returns to the data pair producing means 2 where the above described processing is repeated.
FIG. 5 is a diagram describing in a symbolized manner an example of the data flow program. In FIG. 5, the reference characters N1 and N2 denote two-input and one-output operation node, D1 and D2 denote destination information of input data packets to the respective nodes N1 and N2. The dotted line in the figure indicates depending relation of the data. More particularly, in the figure, the output of the node N1 leads to the left input of the node N2, so that the left input of the node N2 depends on the output of the node N1. It should be noted, however, that there is no data depending relation between the output of the node N1 and the right input of the node N2. Solid circles P1L and P2R in the figure indicate that production of the input data packet to each node is completed. More particularly, in the figure, production of the input data packet P1L to the left input of the node N1 and production of the input data packet P2R to the right input of the node N2 have been completed. In other words, data packet P1L, for example, is produced by reading out the destination information D1 of the node N1 and the instruction information from the program storing means 1, and is waiting for arrival of a data packet P1R to be one of a pair of data in the data pair producing means 2.
For simplicity of explanation, the contents of the color information in the input data packet to the nodes N1 and N2 in FIG. 5 are assumed to be the same. In FIG. 5, the same hash address is produced from the destination information D1 and D2 and, if D1&gt;D2 in value of the contents, the content in the data packet P2R is eventually written into the matching memory in the data pair producing means 2 based on the above described "data exchanging system", without relying on the order of producing the data packets P1L and P2R. On the other hand, the data packet P1L is sent out from the data pair producing means 2, with the through packet flag being set to "valid", and continues to circulate in the information processor shown in FIG. 1 until the data pair to the node N2 is produced. It is noted that the data pair to the node N2 is produced when the input data packet P2L to the left input of the node N2 is produced and inputted to the data pair producing means 2. Then, the data packet P2L is produced, after an operation with respect to the node N1 is executed based on the data depending relation between the nodes N1 and N2, that is, after the data pair for the node N1 is produced. However, since the data packet P2R has been written into the matching memory of the data pair producing means 2, production of the pair to the node N1 can never occur before the data pair to the node N2 is produced.
From the foregoing, it should be appreciated that in the circumstances shown in FIG. 5, deadlock occurs if and when the contents of the color information in the input data packets to the nodes N1 and N2 coincide with each other, the contents D1 and D2 in the destination fields produce the same hash address, and D1 is larger than D2 in value of the contents. Concerning this problem, the above described paper indicates a method of avoiding deadlock caused due to hash collision, by limiting a method of setting destination information in the input data packet, that is, a node number. More particularly, the above described paper proposed that considering any of two-input and one-output nodes having data depending relation in the data flow program, node numbers are set so that destination information of the node to which production of data pair is to be first performed can be always made smaller. For example, in the example shown in FIG. 5, based on the data depending relation, the destination information, that is, the node number is set so that the relation of D1&lt;D2 can be established.
If and when the data flow program to be executed contains no loop structure, deadlock caused due to hash collision can be avoided by adopting the scheme described in the above described paper. However, if the data flow program contains a loop structure, it is likely that the deadlock caused due to hash collision may occur even if the scheme in the above described paper is adopted. FIG. 6 shows an example of a data flow program containing a loop structure. In this figure, the meaning of the reference characters N3, N4, D3, D4 and the solid circle marks P3L and P4R, and the meaning of dotted line are the same those in FIG. 5. In addition, solid square mark P3r in the FIG. 6 indicates a path from an output of the node N3 to the right input of the node N3, that is, an input of any of node group constituting a loop. The P3R becomes eventually a right input data packet P3R of the node N3 as a result of progress of processing. For simplicity of explanation, it is assumed that color information of P3L, P4R and P3r are the same. FIG. 6 shows a circumstance where the right input data packet P4R to the node N4 has being inputted to the data pair producing means 2 before the input data pair to the node N3 is produced. In FIG. 6, the same hash address is produced from the destination information D3 and D4 in the input data packet to the nodes N3 and N4 and, if D3&gt;D4 in value of the contents thereof, deadlock caused due to hash collision occurs on the same ground as that in the case of D1&gt;D2 in FIG. 5. In addition, if, in the data flow program shown in FIG. 6, the same hash address is produced from the destination information D3 and D4 in the input data packet to the nodes N3 and N4, it is possible that the input data packet to the right input of the node N3 is written into the matching memory of the data pair producing means 2, so that deadlock occurs, even if D3&lt;D4, because the nodes N3 and N4 in the data flow program have relation depending on each other.
From the foregoing, it should be appreciated that if a data flow program containing a loop structure is executed, deadlock caused due to hash collision can not the avoided only by the scheme shown in the above described paper.